package outoforder.leetcode;

/**
 * @author shhjiang_001
 * @create 2020-07-04 20:07
 */
// 凑硬币
public class Solution518 {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // 金额为0的时候，凑法有1种
        for (int i = 0; i < n+1; i++) {
            dp[i][0] = 1;
        }
        // 外层循环代表有多少硬币供选择
        for (int i = 1; i <= n; i++) {
            // 内层代表要凑的金额
            for (int j = 1; j <= amount; j++) {
                if (j-coins[i-1]>=0){
                    dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]];
                }else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }

        }
        return dp[n][amount];
    }
}
